package com.fang.algorithm.zuo.dp;

/**
 * @author lingxiao.fang
 * @Desc 机器人在1-N上移动问题
 * 遇到1或者N的时候，只能向左或者向右走，在中间位置可以两个方向走
 * 给定N，机器人在M位置，可以走K步，移动到P点，有多少种走法
 * 1-N上，M、K、P满足1<=M<=N，1<=K<=N，1<=P<=N
 * @createTime 2025/3/16 16:54
 */
public class Test01_BotMoveLocation {

    public static void main(String[] args) {
        int N = 7;
        int M = 3;
        int K = 4;
        int P = 5;
        int num = processMove(N, M, K, P);
        System.out.println(num);
    }

    /**
     *
     * @param N 固定长度
     * @param M 当前位置
     * @param K 剩余步数
     * @param P 固定位置
     * @return
     */
    private static int processMove(int N, int M, int K, int P) {
        if (K == 0) {
            return M == P ? 1 : 0;
        }
        if (M == 1) {
            return processMove(N, M + 1, K - 1, P);
        }
        if (M == N) {
            return processMove(N, M - 1, K - 1, P);
        }
        return processMove(N, M - 1, K - 1, P) + processMove(N, M + 1, K - 1, P);
    }
}
